Recently, for example, studies in the communication field, including mobile communication and deep space communication, and the broadcasting field, including terrestrial-wave broadcasting and satellite digital broadcasting, have advanced remarkably. With this advancement, studies on coding theory have also greatly advanced for the purpose of efficient error-correcting coding and decoding.
A known theoretical limit of code performance is the Shannon limit of the so-called Shannon's channel coding theorem (C. E. Shannon).
The goal of studies on coding theory is to develop coding that exhibits performance near the Shannon limit. A recently developed coding technique approaching the Shannon limit is a technique called Turbo coding, for example, parallel concatenated convolutional codes (PCCC) or serially concatenated convolutional codes (SCCC).
While such turbo codes have been developed, well-known coding of low-density parity check codes (hereinafter referred to as LDPC codes) has attracted attention.
The LDPC codes were first proposed by R. G. Gallager in R. G. Gallager, “Low-Density Parity-Check Codes”, Cambridge, Mass.: M.I.T. Press, 1963, and were rediscovered in D. J. C. MacKay, “Good error correcting codes based on very sparse matrices”, submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399–431, 1999; M. G. Luby, N. Mitzenmacher, N. A. Shokrollahi, and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs”, Proceedings of the 30th ACM STOC. May 23–26, 1998.
Recent studies on the LDPC codes have found that, like the turbo codes, the performance approaches the Shannon limit as the code length increases. Due to the property that the minimum distance is in proportion to the code length, advantageously, the features of the LDPC codes are that the block error probability characteristics are better and the so-called error floor normally observed with decoding of turbo codes substantially does not occur.
The LDPC codes will be described hereinbelow in detail. The LDPC codes are linear codes, and are not necessarily binary; however, the following description will be made in the context of binary LDPC codes.
The greatest feature of the LDPC codes is that the codes are defined by a sparse check matrix. The sparse matrix means that the number of “1s” in this matrix is very small, and may be, for example, a sparse check matrix represented by “H”, shown in FIG. 14, of which the Hamming weight of each column is 3 and the Hamming weight of each row is 6.
The LDPC codes defined by the check matrix H of which the Hamming weights of each row and column are constant are referred to as regular LDPC codes. On the other hand, the LDPC codes defined by the check matrix H of which the Hamming weights of each row and column are not constant are referred to as irregular LDPC codes.
Coding of the LDPC codes is implemented by generating a generator matrix G based on the check matrix H and by multiplying the generator matrix G by a binary-valued information message to generate a codeword. More specifically, an encoder for performing coding of LDPC codes first determines a generator matrix G which satisfies GHT=0 between a transposed matrix HT of the check matrix H and the generator matrix G to be determined. Where the generator matrix G has a k×n matrix, the encoder multiplies the generator matrix G by an information message of k bits to generate a codeword of n bits. The codeword generated by the encoder is mapped so that a code bit of value “0” is converted into “+1” and a code bit of value “1” is converted into “−1” for transmission. The transmitted codeword is received by a decoder via a predetermined communication channel.
Decoding of the LDPC codes can be implemented by the “Probabilistic Decoding” algorithm proposed by Gallager described above, which is a message-passing algorithm based on belief propagation operating on a so-called Tanner graph consisting of variable nodes (also referred to as message nodes) and check nodes. In the “Probabilistic Decoding”, however, messages exchanged among the nodes are real numbers, and it is therefore necessary to monitor the probability distribution itself of the messages of sequential numbers in order to analytically solve the messages. Thus, very difficult analysis is required.
Therefore, Gallager has proposed algorithm A or algorithm B as an algorithm for decoding LDPC codes.
In general, decoding of LDPC codes is performed according to the procedure shown in FIG. 15. In this example, the received value is represented by U0(u0i), the message output from a check node is represented by uj, and the message output from a variable node is represented by vi. Each message is a real number whose “0” likelihood is expressed by the so-called log likelihood ratio.
In the decoding of LDPC codes, as shown in FIG. 15, first, in step S11, upon reception of the received value U0(u0i), the message uj is set to “0” and an integer k of an iterative decoding counter is also set to “0”.
In the decoding of LDPC codes, then, in step S12, the message vi is determined by computation given by Eq. (1) below based on the received value U0(u0i), and the message uj is determined by computation given by Eq. (2) below based on the determined message vi. Then, in the decoding of LDPC codes, the integer k is incremented by “1”.
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            dv                -                1                                      ⁢                          u              j                                                          (        1        )                                          tan          ⁢                                          ⁢                      h            ⁡                          (                                                u                  j                                2                            )                                      =                              ∏                          i              =              1                                      dc              -              1                                ⁢                      tan            ⁢                                                  ⁢                          h              ⁡                              (                                                      v                    i                                    2                                )                                                                        (        2        )            
In Eqs. (1) and (2), dv and dc are arbitrarily selectable parameters representing the number of “1s” in the vertical direction (column) and the horizontal direction (row) of the check matrix H described above, respectively. For example, in case of a (3, 6) code, dv=3 and dc=6. In Eqs. (1) and (2), the messages input from edges that are to output the messages are not used as product or sum parameters, and the product or sum ranges are up to dv-1 and dc-1. In practice, the computation given by Eq. (2) is performed by preparing in advance a table of functions R given by Eq. (3) below, defined by one output with respect to two inputs v1 and v2 and by sequentially using the functions R as in Eq. (4) as follows:x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1, v2)  (3)uj=R(v1, R (v2, R(v3, . . . R(vdc-2, vdc-1))))  (4)
Then, in the decoding of LDPC codes, in step S13, it is determined whether or not the integer k is greater than N.
In the decoding of LDPC codes, if it is determined that the integer k is not greater than N, the processing from step S12 is repeated; if it is determined that the integer k is greater than N, the process proceeds to step S14.
Then, in the decoding of LDPC codes, in step S14, the message vi as a decoding result to be finally output is determined by computation given by Eq. (5) below, and the result is output. Then, the series of processing steps ends. Unlike Eq. (1), Eq. (5) below is calculated using the messages input from all connected edges.
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                            dv                        ⁢                          u              j                                                          (        5        )            
In such decoding of LDPC codes, for example, in the case of a (3, 6) code, as shown in FIG. 16., messages are exchanged between nodes. The computation given by Eq. (1) is performed in the nodes indicated by “=” shown in FIG. 16, and the computation given by Eq. (2) is performed in the nodes indicated by “+”. Particularly in the algorithm A described above, messages are binarized, and the (dc-1) input messages are exclusive ORed by the “+” nodes, and, if all bit values of the (dv-1) input messages are different from the received value R, the inverted version of the codes is output by the “=” nodes.
In the decoding of LDPC codes, a received value must be initially quantized. In a case where the received value or a message exchanged between nodes is expressed with a low bit number, it is known that the performance changes depending upon the setting of the quantization width.
Typically, decoding of LDPC codes for a low bit number is performed according to the procedure shown in FIG. 17.
In the decoding of LDPC codes, as shown in FIG. 17, first, in step S21, upon reception of the received value U0(u0i), the received value U0(u0i) is quantized with a low bit number, the message vi is set to “u0i”, and an integer k of an iterative decoding counter is set to “0”. In the decoding of LDPC codes, for example, when messages are to be expressed with 2 bits, the received value U0(u0i) is quantized to 3 bits. In the decoding of LDPC codes, the received value U0(u0i) quantized to 3 bits is then quantized to 2 bits for use in determining the message vi.
Then, in the decoding of LDPC codes, in step S22, the message uj is determined based on the message vi, and the message vi is further determined based on the received value U0(u0i) and the determined message uj by computation given by Eq. (1). Then, in the decoding of LDPC codes, the integer k is incremented by “1”.
In the decoding of LDPC codes, as described above, a table of single-output functions of low bit number is produced from two low-bit inputs v1 and v2 in advance, and this table is iteratively used to determine the low-bit message uj. In the decoding of LDPC codes, the message vi, which is determined using Eq. (1), causes the bit number to increase, and therefore quantization to 2 bits is performed.
Then, in the decoding of LDPC codes, in step S23, it is determined whether or not the integer k is greater than N.
In the decoding of LDPC codes, if it is determined that the integer k is not greater than N, the processing from step S22 is repeated; if it is determined that the integer k is greater than N, the process proceeds to step S24.
Then, in the decoding of LDPC codes, in step S24, the message vi to be finally output as a result of decoding is determined, and the result is output. Then, the series of processing steps ends.
In such decoding of LDPC codes, the performance changes depending upon the quantization width for quantization of a received value and messages exchanged between nodes. Furthermore, in the decoding of LDPC codes, the quantization width for determination of the message vi using Eq. (1) also affects the error correction performance.
However, in the decoding of LDPC codes, performance evaluation is not performed based on the quantization width, and optimization of the quantization width has not been suggested. In the decoding of LDPC codes, therefore, optimization of the quantization width would admit an improvement in code performance.
The present invention has been made in view of such a situation, and it is an object of the present invention to provide a decoding device and a decoding method that optimize the quantization width to improve the code performance, thus allowing for high-precision decoding of LDPC codes.